package leetcode;

/**
 * @author caifangyi
 * @date 2022/8/8
 */

import java.util.*;
import java.util.stream.Collectors;

/**
 * 1403. 非递增顺序的最小子序列
 *
 * 给你一个数组 nums，请你从中抽取一个子序列，满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。
 *
 * 如果存在多个解决方案，只需返回 长度最小 的子序列。如果仍然有多个解决方案，则返回 元素之和最大 的子序列。
 *
 * 与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。
 *
 * 注意，题目数据保证满足所有约束条件的解决方案是 唯一 的。同时，返回的答案应当按 非递增顺序 排列。
 *
 * 
 *
 * 示例 1：
 *
 * 输入：nums = [4,3,10,9,8]
 * 输出：[10,9] 
 * 解释：子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。
 * 示例 2：
 *
 * 输入：nums = [4,4,7,6,7]
 * 输出：[7,7,6] 
 * 解释：子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。  
 * 示例 3：
 *
 * 输入：nums = [6]
 * 输出：[6]
 * 
 *
 * 提示：
 *
 * 1 <= nums.length <= 500
 * 1 <= nums[i] <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Day1403 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] num = {4,4,7,6,7};
        List<Integer> integers = solution.minSubsequence(num);
        System.out.println(integers.stream().map(integer -> String.valueOf(integer)).collect(Collectors.joining(",")));
    }

    static class Solution {
        public List<Integer> minSubsequence(int[] nums) {
            //排序，然后算前缀和
            sort(nums);

            int[] arr = new int[nums.length+1];
            int sum = 0;
            for (int i = 0; i < nums.length; i++) {
                arr[i+1] = arr[i]+nums[i];
                sum+=nums[i];
            }

            int i = 0;
            for (; i < arr.length; i++) {
                if(arr[i] > sum - arr[i]){
                    break;
                }
            }
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                list.add( nums[j]);
            }
            return list;
        }

        private void sort(int[] nums) {
            sortReverse(nums, 0, nums.length-1);
        }

        private void sortReverse(int[] nums, int left, int right) {
            if(left >= right){
                return;
            }
            int p = getPositoin(nums, left, right);
            if(p!=left)sortReverse(nums, left, --p);
            if(p!=right)sortReverse(nums, ++p, right);
        }

        private int getPositoin(int[] nums, int left, int right) {
            int index = new Random().nextInt(left, right);
            swap(nums, index, right);
            int l = left, r = right;
            int p = l;
            while(l <= r){
                if(nums[l] > nums[right]){
                    swap(nums, l, p++);
                }
                l++;
            }
            swap(nums, right, p);
            return p;
        }

        private void swap(int[] nums, int left, int right) {
            if(left == right){
                return;
            }
            nums[left] = nums[left] ^ nums[right];
            nums[right] = nums[left] ^ nums[right];
            nums[left] = nums[left] ^ nums[right];
        }
    }
}
